package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-11-17 20:56
 */

import java.util.HashMap;
import java.util.Set;

/**
 * 题目：
 * 给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，
 * 并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
 * <p>
 * 示例：
 * 输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
 * 输出: 16
 * 解释: 这两个单词为 "abcw", "xtfn"。
 *  
 */
public class Test80_最大单词长度乘积 {
    public int maxProduct(String[] words) {
        int len = words.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            int tmp = 0;
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                tmp |= 1 << (word.charAt(j) - 'a');
            }
            if (word.length() > map.getOrDefault(tmp, 0)) {
                map.put(tmp, word.length());
            }
        }

        int max = 0;
        Set<Integer> set = map.keySet();
        for (int s : set) {
            int wordlen = map.get(s);
            for (int s2 : set) {
                if ((s & s2) == 0) {
                    max = Math.max(max, wordlen * map.get(s2));
                }
            }
        }
        return max;
    }
}
